We present a probabilistic divide-and-conquer (PDC) method for \emph{exact}sampling of conditional distributions of the form $\mathcal{L}( {\bf X}\, |\,{\bf X} \in E)$, where ${\bf X}$ is a random variable on $\mathcal{X}$, acomplete, separable metric space, and event $E$ with $\mathbb{P}(E) \geq 0$ isassumed to have sufficient regularity such that the conditional distributionexists and is unique up to almost sure equivalence. The PDC approach is todefine a decomposition of $\mathcal{X}$ via sets $\mathcal{A}$ and$\mathcal{B}$ such that $\mathcal{X} = \mathcal{A} \times \mathcal{B}$, andsample from each separately. The deterministic second half approach is toselect the sets $\mathcal{A}$ and $\mathcal{B}$ such that for each element$a\in \mathcal{A}$, there is only one element $b_a \in \mathcal{B}$ for which$(a,b_a)\in E$. We show how this simple approach provides non-trivialimprovements to several conventional random sampling algorithms incombinatorics, and we demonstrate its versatility with applications to samplingfrom sufficiently regular conditional distributions.
展开▼
